#ifndef MARKOV_PREDICTOR_H
#define MARKOV_PREDICTOR_H

//这里使用基于markov的算法，我们将最近的100w次访问作为访问模式的依据，当然这个100w的值是可调的。我们抛弃“转化矩阵”的实现方式
//将历史的访问后继的技术集合作为一个属性放到一个数据块的元数据中
#include<memory.h>
#include<stdio.h>
#include<stdlib.h>

#define MAX_MARKOV_BARREL_NUM 10000
#define MAX_MARKOV_BARREL_SIZE 100
#define MAX_MARKOV_HISTORY_SIZE 10000000
#define MARKOV_PREDICTOR_DEEP 6
#define MAX_MARKOV_EACH_HISTORY_DEEP 5

//用一个数据结构来记录某一个块的后继的次数，使用一个链表结构来记录
typedef struct _markov_block_successor_counter_item{
    //用一个链表将头尾相连
    struct _markov_block_successor_counter_item* front;
    struct _markov_block_successor_counter_item* next;

    //当前节点的块号
    long block_num;
    //后继
    long successor_num;
    //数量
    int count;
}markov_block_successor_counter_item_t;

//一个节点的元数据
//这里的元数据是依照先来后到的顺序排列，
typedef struct _markov_block_meta_item{
    //将元数据也要头尾相连
    struct _markov_block_meta_item* front;
    struct _markov_block_meta_item* next;

    //当前块号
    long block_num;
    //当前节点的链表头结点
    markov_block_successor_counter_item_t* head;
    //元数据的数量
    long size;
} markov_block_meta_item_t;

//一个历史记录节点
typedef struct _markov_history_meta_item{
    //用一个双向链表
    struct _markov_history_meta_item* front;
    struct _markov_history_meta_item* next;
    
    //目标节点
    long target_block;
    //目标节点的后继
    long success_block;
} markov_history_meta_item_t;



//一个元数据吃，我们创建10000个桶，每个桶里面有平均最多100个元素
//这些元数据的淘汰是和在10000位的历史记录中还有没有这个元素有关
//也就是说如果我们发现一个元素已经没有发现的后继了，就把他删除。
typedef struct _markov_block_predictor{
    //用一个桶来存储所有的markov元数据，需要初始化，这个相当于一系列头指针
    markov_block_meta_item_t block_metas[MAX_MARKOV_BARREL_NUM];

    //这里用一个链表来存储100w位的历史记录
    markov_history_meta_item_t* history_head;

    //这里记录一下历史记录的个数
    long history_size;

    //这里要让每个桶中的元素单独计数
    long size[MAX_MARKOV_BARREL_NUM];
} markov_block_predictor_t;

void init_markov_block_meta_item(markov_block_meta_item_t* markov_block_meta_item, long block_num);

void init_markov_block_meta(markov_block_predictor_t* markov_block_meta);

markov_block_meta_item_t* markov_add_new_item_in_barrel(markov_block_meta_item_t* block_meta_head, long block_num, long* barrel_size);

void markov_add_new_success_history(markov_block_meta_item_t* target_block, long history);

markov_block_meta_item_t* markov_search_block_meta_in_barrel(markov_block_meta_item_t* barrel_head, long block_num);

int markov_get_barrel_from_block(long block_num);

void markov_del_old_success_history(markov_block_meta_item_t* target_block, long history, long* size);

markov_history_meta_item_t markov_add_history(markov_history_meta_item_t* history_head, long block_num, long history, long* history_size);

long markov_find_max_successor(markov_block_meta_item_t* target_block);

void markov_predictor(markov_block_predictor_t* block_predictor, long* return_arr, int* size, long now_access);



#endif